1. Field of the Invention
The present invention relates generally to pseudorandom number sequence generators, and more specifically to a pseudorandom number sequence generator, or nonlinear feedback shift register, suitable for producing stream ciphers.
2. Description of the Related Art
Stream ciphers are used to scramble important data to protect it from being tapped or tampered with by unauthorized attempts. Nonlinear feedback shift registers are most often used to produce a pseudorandom number (PN) sequence. Details of this type of nonlinear feedback shift register are described in "Analysis and Design of Stream Ciphers", R. A. Rueppel, Springer-Verlag, 1986. The prior art nonlinear feedback shift register is based on a Hamiltonian graph which is concerned with the possibility of travelling around a graph, going along branches (edges) in such a way as to visit every node (vertex) exactly once. Usually, a trial-and-error method is used to discover a Hamiltonian cycle if the shift register has a small number of stages. However, the trial-and-error method is impractical for a shift register if it is required to produce a PN sequence of long period. In addition, if a Hamiltonian cycle were found, the resultant PN sequence would contain a substantially equal number of 0's and 1's which cannot be logically compressed for implementation of simple circuitry.